public class Test2 {
    private final int[] x = {-1,0,0,1};
    private final int[] y = {0,-1,1,0};
    private boolean[][] vis;
    public boolean exist (String[] board, String word) {
        // write code here
        int len1 = board.length;
        int len2 = board[0].length();
        char[][] cc = new char[len1][len2];
        vis = new boolean[len1][len2];
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                cc[i][j] = board[i].charAt(j);
            }
        }
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (cc[i][j] == word.charAt(0)) {
                    if (dfs(cc, i, j, 1, word)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] cc, int row, int col, int index, String word) {
        if (index >= word.length()) {
            return true;
        }
        for (int i = 0; i < 4; i++) {
            int newRow = row + x[i];
            int newCol = col + y[i];
            if (newRow >= 0 && newRow < cc.length && newCol >= 0 && newCol < cc[0].length
                    && cc[newRow][newCol] == word.charAt(index) && !vis[newRow][newCol]) {
                vis[newRow][newCol] = true;
                if (dfs(cc, newRow, newCol, index+1, word)) {
                    return true;
                }
                vis[newRow][newCol] = false;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        String[] board = {"XYZE","SFZS","XDEE"};
        String word = "XYZZED";
        Test2 t = new Test2();
        System.out.println(t.exist(board, word));
    }
}
